Decision trees and decision forests (which are collections of many trees) are used in machine learning applications to make decisions or predictions based on input data, which may be observations about an item. The decision trees are created by learning from large sets of training data which may have been manually classified or otherwise analyzed to produce ‘ground truth’ data. An example of a machine learning application may be object recognition in images or videos. In such an example, the ground truth data may comprise labeled images. As decision forests contain many decision trees, the time and computational power taken to evaluate a forest can be large which limits their use, particularly in real time applications. Training decision trees is also a very intensive process and generating a decision tree can take days or weeks, depending on the complexity of the particular machine learning application.
CPUs (Central Processing Units) are currently used to train and evaluate decision trees. CPUs are designed to have general processing capability and as a result are very flexible in their application and the way they can be programmed; however, they are not designed for parallel computation. Many desktop computers also contain a GPU (Graphics Processing Unit) which has a highly parallel structure and is designed specifically to perform graphics operations, including rendering polygons and texture mapping. Recent GPUs include programmable stages known as shaders: a vertex shader and a pixel shader. The vertex shader is used to modify the vertices of a polygon, e.g. moving a vertex to change the shape of an object. The pixel (or fragment) shader reads and writes pixel values and is used to change the appearance of a pixel (i.e. its color) based on parameters such as lighting, shading etc. By performing the graphics operations in dedicated hardware (i.e. the GPU) rather than in the CPU, the operations can be performed much more quickly. However, as the GPU is not designed for general use, it is not flexible like the CPU and has a number of limitations. This has the result that it is not straightforward to design systems and algorithms that can make use of the GPU for other, non-graphics operations.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known methods of evaluating decision trees.